#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

int n,mod,k,r;

struct matrix{
	ll arr[55][55];
	matrix(){memset(arr,0,sizeof(arr));}
	const ll * operator [](int x)const{return arr[x];}
	ll * operator [](int x){return arr[x];}
	friend matrix operator * (matrix a,matrix b){
		matrix c;
		for(int i = 0;i < k;i++)
			for(int j = 0;j < k;j++)
				if(a[i][j])
					for(int kk = 0;kk < k;kk++)
						(c[i][kk] += a[i][j] * b[j][kk] % mod) %= mod;
		return c;
	}
}f,per;

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,mod = in,k = in,r = in;
	f[0][0] = 1;
	ll tt = 1ll * n * k;
	for(int i = 0;i < k;i++)
		per[i][i]++,per[i][(i+1)%k]++;
	for(;tt;tt >>= 1,per = per * per) if(tt & 1) f = f * per;
	printf("%lld\n",f[0][r]);
	return 0;
}

